updated: 2022-01-23_12:32:31-05:00

Nondeterministic Finite Automata

Formal Definition:

  • A nondeterministic finite automaton is a 5-tuple $(Q,\Sigma, \delta, q_0,f)$ where
    1. Q is a finite set of states
    2. $\Sigma$ is a finite alphabet
    3. $\delta:Q\times {\Sigma}_e\rightarrow P(Q)$
    • $\Sigma _e=\Sigma \cup {e}$
    1. $q_0 \in Q$ is the start state
    2. $f\leq Q$ is set of accept states

^ e is $\epsilon$

Combining DFA's to become NFA

Closure Properties of regular languages using NFA:

  1. Union:

    • given two regular languages l1 and l2

    • two NFA for then 2 regular languages n1 and n2

    • construct L1 $\cup$ L2 -> n1, $\cup$ n2

    • Epsilon transitions to each

      • Pasted image 20210917093804

    • Proof:photo_2021-09-17_09-45-01

  2. Concatenation: success state -> epsilon transition to -> start states of next

    • operation: accept states have epsilon transition to start state

Examples

Example: Writing a NFA formally:

Pasted image 20210917093136

Example: Finite Automata that accepts all strings of form $0^k$ where k is a multiple of 2 or 3

  • Pasted image 20210915095411

Example: the language of strings of length at least 2 that begin with 0 and end in 1:

Pasted image 20210915100049

  • NOTE: When a state has no transitions, if you have more inputs it will fail automatically

Example: the language of strings of length at least 2 that have a 1 in the second to last position

Pasted image 20210917091923